#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=4e5+10;
vector<pii> g[N];
int st[N];
int num[N][31];
int cnt[40];
int sum;
void dfs(int u)
{
    st[u]=1;
    sum++;
    for(int i=0;i<=30;i++) cnt[i]+=num[u][i];
    for(auto [i,val]:g[u])
    {
        if(st[i]==0)
        {
            for(int j=0;j<=30;j++)
            {
                if((val>>j)&1)
                {
                    num[i][j]=(!num[u][j]);
                }
                else num[i][j]=num[u][j];
            }
            dfs(i);
        }
        else
        {
            for(int j=0;j<=30;j++)
            {
                if((num[u][j]^num[i][j])!=((val>>j)&1))
                {
                    cout<<-1;
                    exit(0);
                }
            }
        }
    }
} 
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(st[i]==0)
        {
            sum=0;
            for(int j=0;j<=30;j++) cnt[j]=0;
            dfs(i);
            for(int j=0;j<=30;j++)
            {
                ans+=min(cnt[j]*(1ll<<j),(sum-cnt[j])*(1ll<<j));
            }
        }
    }
    cout<<ans;
    return 0;
}
